#include <iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isFather(TreeNode *root, TreeNode *p);

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q) return root;
        // 这里要求pq必须为root的子节点
        bool left = isFather(root->left, p);
        auto right = isFather(root->right, q);
        if (left ^ right) { // 若两者在同一边
            return lowestCommonAncestor(left ? root->left : root->right, p, q);
        } else {
            return root;
        }
    }
};

bool Solution::isFather(TreeNode *root, TreeNode *p) {
    if (root == p) {
        return true;
    }
    if (root == nullptr) {
        return false;
    }
    return isFather(root->left, p) || isFather(root->right, p);
}

int main() {
    std::cout << "Hello, World!" << std::endl;
    // createTree
    TreeNode nodes[20];
    for (int i = 0; i < 20; ++i) {
        nodes[i] = TreeNode{i};
    }

    for (int i = 1; 2*i + 1 < 16; ++i) {
        nodes[i].left = &nodes[2 * i];
        nodes[i].right = &nodes[2 * i + 1];
    }

    cout << Solution().lowestCommonAncestor(&nodes[1], &nodes[2], &nodes[1]) -> val;
    return 0;
}